package linkedlist;

//此处我们实现双向链表
public class MyDLinkedList {
    static class Node {//内部类
        public String val;
        public Node prev;
        public Node next;
        public Node(String val) {
            this.val = val;
            this.prev = null;
            this.next = null;
        }
        }
        //表示整个链表，此处不引入傀儡节点，使用null来表示空节点
        private Node head=null;//为头节点
        private Node tail=null;//为节点

    //实现链表的一些核心操作
    //头插
    public void addFirst(String val){
        //从创建新节点开始
        Node newNode=new Node(val);
        if(head==null){
            //链表为空，则头节点和尾节点都指向新节点
            head=newNode;
            tail=newNode;
        }else{
            //链表不为空，则新节点的next指向头节点，头节点的prev指向新节点
            newNode.next=head;
            //
            head.prev=newNode;
            //更新头节点+
            head=newNode;
        }
    }
    //尾插
    public void addList(String val){
        //从创建新节点开始
        Node newNode=new Node(val);
        if(head==null){
                //链表为空，则头节点和尾节点都指向新节点
            head=newNode;
            tail=newNode;
        }else{
            //链表不为空，则新节点的prev指向尾节点，尾节点的next指向新节点
            newNode.prev=tail;
            tail.next=newNode;
            //更新尾节点
            tail=newNode;
        }
    }
    //指定位置插入
    public void add(int index,String val){
        int size=size();
        if(index<0||index>size){//是否=size()需要考虑
            throw new IndexOutOfBoundsException("输入无效参数");
        }
        //index=0，则头插
        if(index==0){
            addFirst(val);
            return;
            //index=size，则尾插
        }else if(index==size){
            addList(val);
            return ;
            //index在中间，则遍历到指定位置，插入节点
        }else {
            Node newNode = new Node(val);
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            //将新节点插入到prev和prev.next之间
            //新节点的next指向prev.next
            //原本prev.next的指向下一个节点，然后将新节点插入，用新节点的next指向原来的下一个节点
            newNode.next = prev.next;
            //prev的next指向新节点
            //插入后面的节点要与新节点链接起来，然后用prev.next.prevd表示第插入节点的后一个节点。然后与新节点链接起来。
            prev.next.prev = newNode;
            //新节点的prev指向prev
            //由于是双向链表，所以新节点的perv指向perv。
            newNode.prev = prev;
            //然后用prev.next指向新节点。
            prev.next=newNode;
        }
    }
    public int size(){
        int size=0;
        for(Node node=head;node!=null;node=node.next){
            size++;
        }
        return size;
    }

    //查找元素是否存在
    public Boolean contains(String val) {
        for (Node node = head; node != null; node = node.next) {
            if (node.val.equals(val)) {
                return true;
            }
        }
        return false;
    }
    //查找元素，返回元素下标，没有则返回-1
    public int indexOf(String val) {
        int index=0;
        for (Node node = head; node != null; node = node.next) {
            if (node.val.equals(val)) {
                return index;
            }
            index++;
        }
        return -1;
    }
    //删除头部元素
    public void removeFist(){
        //先判断链表是否为空
        if(head==null){
            return ;
        }
        if(head.next==null){
            head=null;
            tail=null;
        }else{
            //链表不为空，则删除头节点head
            //先让头节点指向下一个节点
            head=head.next;
            //让头节点的prev指向null
            head.prev=null;
        }
    }

    //删除尾部元素
    public void removeLast() {
        //先判断链表是否为空
        if (head == null) {
            return;
        }
        if(head.next==null){
            head=null;
            tail=null;
        }
        else {
            //链表不为空，则删除尾节点tail
            //先找到尾节点的前一个节点
            tail = tail.prev;
            //然后将尾节点的前一个节点的next指向null
            tail.next=null;

        }
    }
    //删除指定位置元素
    public void remove(int index) {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException("输入无效参数");
        }
        if (index == 0) {
            removeFist();
        } else if (index == size() - 1) {
            removeLast();
        } else {
            Node prev = head;
            for(int i=0;i<index-1;i++){
                prev=prev.next;
            }
            //（1）
            //指向要删除的节点
            Node delNode=prev.next;
            //指向要删除的节点的下一个节点
            Node nextNode=delNode.next;

            //（2）
            //将prev的next指向nextNode
            prev.next=nextNode;
            //将nextNode的prev指向prev
            nextNode.prev=prev;
        }
    }
    //指定值删除元素
    public void remove(String val) {
        //判读链表是否为空
        if(head==null){
            return ;
            //判断是否是头节点
        }else if(head.val.equals(val)){
            removeFist();
            return ;
            //判断是否是尾节点
        }else if(tail.val.equals(val)){
            removeLast();
            return ;
            //遍历链表，找到要删除的节点
        }else{
            Node toremove=head;
            for(;toremove!=null;toremove=toremove.next) {
                if (toremove.val.equals(val)) {
                    break;
                }
            }
            if(toremove==null){
                //没有找到要删除的元素
                return;
            }
            //将周到的节点的prev和next指向要删除的节点的前一个节点和下一个节点
            Node prev= toremove.prev;
            Node next=toremove.next;

            //这个其实就是链接链表的操作
            //将prev的next指向next
            prev.next=next;
            //将next的prev指向prev
            next.prev=prev;
        }

    }
    //clear方法，清空链表
    public void clear(){
        head=null;
        tail=null;
    }
    //打印链表与单向没有区别
    @Override
    public  String  toString(){
        StringBuilder stringbuilder=new StringBuilder();
        stringbuilder.append("[");
        for(Node node=head;node!=null;node=node.next){
            stringbuilder.append(node.val);
            if(node.next!=null){
                stringbuilder.append(",");
            }
        }
        stringbuilder.append("]");
        return stringbuilder.toString();
    }


    public static void test1(){
        MyDLinkedList list=new MyDLinkedList();
        list.addFirst("a");
        list.addFirst("b");
        list.addFirst("c");
        System.out.println(list.toString());//输出结果：[c, b, a]
    }
    public static void test2(){
        MyDLinkedList list=new MyDLinkedList();
        list.addList("a");
        list.addList("b");
        list.addList("c");
        System.out.println(list.toString());//输出结果：[a, b, c]
    }
    public static void test3(){
        MyDLinkedList list=new MyDLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.add(1,"e");
        System.out.println(list.toString());//·输出结果：[a, e, b, c, d]

    }
    public static void test4(){
        MyDLinkedList list=new MyDLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        System.out.println(list.contains("a"));//输出结果：true
        System.out.println(list.contains("e"));//输出结果：false
    }
    public static void test5(){
        MyDLinkedList list=new MyDLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        System.out.println(list.indexOf("a"));//输出结果：0
        System.out.println(list.indexOf("e"));//输出结果：-1
    }
    public static void test6(){
        MyDLinkedList list=new MyDLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.removeFist();
        System.out.println(list.toString());//输出结果：[b, c, d]
    }
    public static void test7(){
        MyDLinkedList list=new MyDLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.removeLast();
        System.out.println(list.toString());//输出结果：[a, b, c]
    }
    public static void test8(){
        MyDLinkedList list=new MyDLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.remove(1);
        System.out.println(list.toString());//输出结果：[a, c, d]
    }
    public static void test9(){
        MyDLinkedList list=new MyDLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.remove("b");
        System.out.println(list.toString());//输出结果：[a, c, d]
    }
    public static void test10(){
        MyDLinkedList list=new MyDLinkedList();
        list.add(0,"a");
        list.add(1,"b");
        list.add(2,"c");
        list.add(3,"d");
        list.clear();
        System.out.println(list.toString());//输出结果：[]
    }

    public static void main(String[] args) {
         test1();//头插
         test2();//尾插
         test3();//指定位置插入
         test4();//判断元素是否存在
         test5();//查找元素下标
        test6();//删除头部元素
        test7();//删除尾部元素
        test8();//删除指定位置元素
        test9();//指定值删除元素
        test10();//清空链表

    }

}